package com.congee02;

import java.util.*;

public class MaximumSubarraySum_Common {

    public long maximumSubarraySum(int[] nums, int k) {

        Map<Integer, Integer> rightest = new HashMap<>();

        long sum = 0L;
        for (int i = 0 ; i < k ; i ++ ) {
            rightest.put(nums[i], i);
            sum += nums[i];
        }
        long maxSum = rightest.size() == k ? sum : -1L;


        int n = nums.length;
        for (int r = k ; r < n ; r ++ ) {
            int l = r - k + 1;

            int expired = nums[l - 1];
            int come = nums[r];

            sum += - expired + come;

            if (rightest.get(expired) <= l - 1) {
                rightest.remove(expired);
            }
            rightest.put(come, r);

            if (rightest.size() == k && sum > maxSum) {
                maxSum = sum;
            }

        }

        return maxSum;
    }

}
